package 动态规划;

public class NC7股票_一次交易 {

    /**
     * 假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。
     * 你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。
     * 示例1
     * 输入
     * [1,4,2]
     * 返回值
     * 3
     *
     * 示例2
     * 输入
     * [2,4,1]
     * 返回值
     * 2
     */

    //方法一:维护前序天数的minPrices,然后更新最大收益
    //方法二:动态规划,持股+不持股,计算最大收益
    //鼎立推荐方法一
    public int maxProfit (int[] prices) {
        return method1(prices);
    }

    private int method1(int[] prices) {
        if(prices.length<1){
            return 0;
        }
        int minPrices=prices[0];
        int maxResult=0;

        for (int i = 0; i < prices.length; i++) {
            if(minPrices>prices[i]){
                //更新最低点
                minPrices=prices[i];
            }else{
                //更新最大收益
                maxResult=Math.max(maxResult,prices[i]-minPrices);
            }
        }

        return maxResult;
    }

    private int method2(int[] prices) {
        if(prices.length<1){
            return 0;
        }

        //dp代表手上的现金数
        int[][] dp=new int[prices.length][2];
        /**
         * 不持股和持股->不持股
         * 持股->持股
         */
        dp[0][0]=0;
        dp[0][1]=-prices[0];

        for (int i = 1; i < prices.length; i++) {
            //dp[i][0]就是最大收益,一直根据持有股票在更新;
            dp[i][0]=Math.max(dp[i][0],dp[i-1][1]+prices[i]);//不持股/卖出
            dp[i][1]=Math.max(dp[i][1],-prices[i]);
        }

        return dp[prices.length-1][0];
    }

    public static void main(String[] args) {
        NC7股票_一次交易 n=new NC7股票_一次交易();
        int[] arr={2,1,4};
        int result = n.maxProfit(arr);
        System.out.println(result);
    }

}
